package com.mashibing.class13;

/**
 * 使用套路判定完全二叉树。
 * 完全二叉树的判定规则:
 * 1) 左满 右满  左高=右高  满完全二叉树
 * 2) 左完全二叉树 右满  左高 = 右高 + 1
 * 3) 左满  右满    左高 = 右高 + 1
 * 4) 左满  右完全   左高 = 右高
 */
public class Code01_IsCBT {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static class Info{
        public boolean isFull;
        public boolean isCBT;
        public int height;

        public Info(boolean isFull, boolean isCBT, int height) {
            this.isFull = isFull;
            this.isCBT = isCBT;
            this.height = height;
        }
    }

    public static boolean isCBT(Node head){
        return process(head).isCBT;
    }

    public static Info process(Node node){
        if (node==null){
            return new Info(true,true,0);
        }
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1 ;
        boolean isFull = leftInfo.isFull&& rightInfo.isFull&&(leftInfo.height== rightInfo.height);
        boolean isCBT = false;
        // 可能性1
        if (leftInfo.isFull&& rightInfo.isFull&& (leftInfo.height == rightInfo.height)){
            isCBT = true;
        }
        // 可能性 2
        else if (leftInfo.isCBT&& rightInfo.isFull&&(leftInfo.height == rightInfo.height+1)){
            isCBT = true;
        }
        // 可能性 3
        else if (leftInfo.isFull&& rightInfo.isFull&&(leftInfo.height == rightInfo.height+1)){
            isCBT = true;
        }
        // 可能性 4
        else if (leftInfo.isFull&& rightInfo.isCBT&&(leftInfo.height == rightInfo.height)){
            isCBT = true;
        }
        return new Info(isFull,isCBT,height);
    }
}
